import java.util.LinkedList;
import java.util.Queue;

public class Solution4 {
    public static void main(String[] args) {
        Solution4 solution4 = new Solution4();
        char[][] board = {{'X','X','X','X'},
                          {'X','O','O','X'},
                          {'X','X','O','X'},
                          {'X','O','X','X'}};
        solution4.solve(board);
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }
    int m;
    int n;
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    Queue<int[]> q;
    public void solve(char[][] board) {
        m = board.length;
        n = board[0].length;
        q = new LinkedList<>();

        // 1. 把边缘的  O 初始化为 .
        for(int j = 0; j < n; j++) {
            if(board[0][j] == 'O') {
                q.add(new int[]{0, j});
                board[0][j] = '.';
                bfs(board);
            }
            if(board[m - 1][j] == 'O') {
                q.add(new int[]{m - 1, j});
                board[m - 1][j] = '.';
                bfs(board);
            }
        }
        for(int i = 0; i < m; i++) {
            if(board[i][0] == 'O') {
                q.add(new int[]{i, 0});
                board[i][0] = '.';
                bfs(board);
            }
            if(board[i][n - 1] == 'O') {
                q.add(new int[]{i, n - 1});
                board[i][n - 1] = '.';
                bfs(board);
            }
        }

        // 2. 还原
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i][j] == 'O') {
                    board[i][j] = 'X';
                }else if(board[i][j] == '.') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    public void bfs(char[][] board) {
        while(!q.isEmpty()) {
            int[] t = q.poll();
            int a = t[0];
            int b = t[1];
            for(int k = 0; k < 4; k++) {
                int x = a + dx[k];
                int y = b + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {
                    board[x][y] = '.';
                    q.add(new int[]{x, y});
                }
            }
        }
    }
}
